๐Ÿ‘ฉโ€๐Ÿ’ป 76502. ๊ด„ํ˜ธ ํšŒ์ „ํ•˜๊ธฐ

@Seongukbaek Posted August 09, 2022 ยท Updated August 09, 2022 ยท 2 min read

๋ฌธ์ œ

Programmers - ๊ด„ํ˜ธ ํšŒ์ „ํ•˜๊ธฐ

๐Ÿ“ Logic

// ์ฃผ์–ด์ง„ ์ธ๋ฑ์Šค ์‚ฌ์ด์˜ ๋ฌธ์ž์—ด์ด ์˜ฌ๋ฐ”๋ฅธ ๋ฌธ์ž์—ด์ธ์ง€ ํŒ๋‹จ private boolean isValid(int s, int e) { if (s == e) return true; for (int i = s; i < e; i++) { char ch = str.charAt(i); if (stack.isEmpty()) { if (isCloseCh(ch)) return false; stack.add(ch); } else { char stCh = stack.peek(); if (isPair(stCh, ch)) stack.pop(); else if (isCloseCh(ch)) return false; else stack.add(ch); } } return true; }
  • ์‹œ์ž‘ ์ธ๋ฑ์Šค์™€ ๋ ์ธ๋ฑ์Šค๋ฅผ ์ธ์ž๋กœ ๋ฐ›์•„, ํ•ด๋‹น ์ธ๋ฑ์Šค ์‚ฌ์ด์˜ ๋ฌธ์ž์—ด์ด ์˜ฌ๋ฐ”๋ฅธ์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜
  • ์Šคํƒ์„ ์‚ฌ์šฉํ•ด ๊ด„ํ˜ธ ๋ฌธ์ž์˜ ์Œ์ด ๋งž๋‹ค๋ฉด ์Šคํƒ์—์„œ ์ œ๊ฑฐํ•˜๊ณ , ๊ทธ๋ ‡์ง€ ์•Š๊ณ  ๋‹ซํžŒ ๊ด„ํ˜ธ๋ผ๋ฉด ์˜ฌ๋ฐ”๋ฅด์ง€ ์•Š์Œ์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Solution { private String str; private Stack<Character> stack; public int solution(String s) { this.str = s; int len = s.length(); int answer = 0; if (len % 2 == 1) return answer; for (int i = 0; i < len; i++) { stack = new Stack<>(); // i๋ถ€ํ„ฐ ๋ฌธ์ž์—ด ๊ธธ์ด๊นŒ์ง€๊ฐ€ ์˜ฌ๋ฐ”๋ฅด๋‹ค๋ฉด, 0๋ถ€ํ„ฐ i๊นŒ์ง€ ์˜ฌ๋ฐ”๋ฅธ์ง€ ํ™•์ธ if (isValid(i, len)) answer += isValid(0, i) ? 1 : 0; } return answer; } // ์ฃผ์–ด์ง„ ์ธ๋ฑ์Šค ์‚ฌ์ด์˜ ๋ฌธ์ž์—ด์ด ์˜ฌ๋ฐ”๋ฅธ ๋ฌธ์ž์—ด์ธ์ง€ ํŒ๋‹จ private boolean isValid(int s, int e) { if (s == e) return true; for (int i = s; i < e; i++) { char ch = str.charAt(i); if (stack.isEmpty()) { if (isCloseCh(ch)) return false; stack.add(ch); } else { char stCh = stack.peek(); if (isPair(stCh, ch)) stack.pop(); else if (isCloseCh(ch)) return false; else stack.add(ch); } } return true; } private boolean isCloseCh(char ch) { return ch == '}' || ch == ']' || ch == ')'; } private boolean isPair(char stCh, char ch) { return (stCh == '(' && ch == ')') || (stCh == '{' && ch == '}') || (stCh == '[' && ch == ']'); } }

โœ๏ธ Review

  • ๊ด„ํ˜ธ๋Š” ํ•ญ์ƒ ์ง์ด ๋งž๋Š”์ง€์— ๋Œ€ํ•œ ๋กœ์ง์ด ํ•„์š”ํ•˜๊ณ , ์ด๋ฅผ ๊ตฌํ˜„ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์Šคํƒ์ด ์ œ๊ฒฉ์ด๋ผ ์ƒ๊ฐํ–ˆ๋‹ค.
  • ๊ธˆ๋ฐฉ ํ’€๋ฆฐ ๋ฌธ์ œ
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€